
package main

import "fmt"

func solution(m int, n int, a [][]int) int {
	vis := make([][]int, m)
	for i := range vis {
		vis[i] = make([]int, n)
	}

	var dfs func(x, y, k int) int
	dfs = func(x, y, k int) int {
		ans := 0
		directions := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

		for _, dir := range directions {
			nx, ny := x+dir[0], y+dir[1]
			if nx < 0 || ny < 0 || nx >= m || ny >= n || vis[nx][ny] == 1 {
				continue
			}

			if (k == 0 && a[nx][ny] <= a[x][y]) || (k == 1 && a[nx][ny] >= a[x][y]) {
				continue
			}

			vis[x][y] = 1
			current := dfs(nx, ny, k^1) + 1
			if current > ans {
				ans = current
			}
			vis[x][y] = 0
		}
		return ans
	}

	res := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if current := dfs(i, j, 0); current > res {
				res = current
			}
			if current := dfs(i, j, 1); current > res {
				res = current
			}
		}
	}
	return res
}

func main() {
	fmt.Println(solution(2, 2, [][]int{{1, 2}, {4, 3}}) == 3)
	fmt.Println(solution(3, 3, [][]int{{10, 1, 6}, {5, 9, 3}, {7, 2, 4}}) == 8)
	fmt.Println(solution(4, 4, [][]int{{8, 3, 2, 1}, {4, 7, 6, 5}, {12, 11, 10, 9}, {16, 15, 14, 13}}) == 11)
}
